package algorithms.tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author lizen
 */
public class BinaryTree {
    private TreeNode root;

    public BinaryTree() {
        root = null;
    }

    // 插入节点（简单的二叉搜索树插入方式）
    public void insert(int val) {
        root = insertRecursive(root, val);
    }

    private TreeNode insertRecursive(TreeNode current, int val) {
        if (current == null) {
            return new TreeNode(val);
        }

        if (val < current.val) {
            current.left = insertRecursive(current.left, val);
        } else if (val > current.val) {
            current.right = insertRecursive(current.right, val);
        }

        return current;
    }

    // 前序遍历
    public void preOrderTraversal() {
        preOrderRecursive(root);
    }

    private void preOrderRecursive(TreeNode node) {
        if (node != null) {
            System.out.print(node.val + " ");
            preOrderRecursive(node.left);
            preOrderRecursive(node.right);
        }
    }

    // 中序遍历
    public void inOrderTraversal() {
        inOrderRecursive(root);
    }

    private void inOrderRecursive(TreeNode node) {
        if (node != null) {
            inOrderRecursive(node.left);
            System.out.print(node.val + " ");
            inOrderRecursive(node.right);
        }
    }

    // 后序遍历
    public void postOrderTraversal() {
        postOrderRecursive(root);
    }

    private void postOrderRecursive(TreeNode node) {
        if (node != null) {
            postOrderRecursive(node.left);
            postOrderRecursive(node.right);
            System.out.print(node.val + " ");
        }
    }

    // 层序遍历（广度优先）
    public void levelOrderTraversal() {
        if (root == null) return;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            TreeNode current = queue.poll();
            System.out.print(current.val + " ");

            if (current.left != null) {
                queue.add(current.left);
            }
            if (current.right != null) {
                queue.add(current.right);
            }
        }
    }

    // 查找节点
    public boolean contains(int val) {
        return containsRecursive(root, val);
    }

    private boolean containsRecursive(TreeNode current, int val) {
        if (current == null) {
            return false;
        }
        if (val == current.val) {
            return true;
        }
        return val < current.val
                ? containsRecursive(current.left, val)
                : containsRecursive(current.right, val);
    }

    // 删除节点
    public void delete(int val) {
        root = deleteRecursive(root, val);
    }

    private TreeNode deleteRecursive(TreeNode current, int val) {
        if (current == null) {
            return null;
        }

        if (val == current.val) {
            // 节点没有子节点
            if (current.left == null && current.right == null) {
                return null;
            }
            // 节点只有一个子节点
            if (current.right == null) {
                return current.left;
            }
            if (current.left == null) {
                return current.right;
            }
            // 节点有两个子节点
            int smallestValue = findSmallestValue(current.right);
            current.val = smallestValue;
            current.right = deleteRecursive(current.right, smallestValue);
            return current;
        }

        if (val < current.val) {
            current.left = deleteRecursive(current.left, val);
            return current;
        }
        current.right = deleteRecursive(current.right, val);
        return current;
    }

    private int findSmallestValue(TreeNode root) {
        return root.left == null ? root.val : findSmallestValue(root.left);
    }

    // 获取树的高度
    public int getHeight() {
        return calculateHeight(root);
    }

    private int calculateHeight(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return 1 + Math.max(calculateHeight(node.left), calculateHeight(node.right));
    }
}
